/**
 * 根据前序中序创建二叉树
 */
class Solution {
    int proindex = 0;
    public TreeNode buildChild(int[] postorder , int[] inorder ,int inbegin , int inend) {
        if(inbegin > inend) return null;

        TreeNode node = new TreeNode(postorder[proindex]);
        int index = indexOf(inorder,inbegin,inend,postorder[proindex]);
        proindex--;

        node.right = buildChild(postorder,inorder,index+1,inend);
        node.left = buildChild(postorder,inorder,inbegin,index - 1);
        

        return node;
    }

    public int indexOf(int[] inorder, int left ,int right,int val) {
            for(int i = left;i <=right;i++) {
                if(inorder[i] == val) {
                    return i;
                }
            }
            return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        proindex = postorder.length-1;
        return buildChild(postorder,inorder,0,inorder.length - 1);
    }

    /**
     *
     * @param root
     * @return 非递归前序遍历
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()) {
            while(cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode tap = stack.pop();
            cur = tap.right;
        }
        return list;
    }

    /**
     *
     * @param root
     * @return 非递归中序遍历
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tap = stack.pop();
            list.add(tap.val);
            cur = tap.right;
        }
        return list;
    }

    /**
     *
     * @param root
     * @return 非递归后序遍历
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;
        TreeNode prev = null;

        while(cur!=null || !stack.empty() ) {
            while(cur != null ) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode Top = stack.peek();
            if(Top.right == null || prev == Top.right) {
                stack.pop();
                list.add(Top.val);
                prev = Top;
            } else {
                cur = Top.right;
            }
        }
        return list;
    }

    /**
     * 根据二叉树创建字符串
     */
    StringBuilder str = new StringBuilder();
    public String tree2str(TreeNode root) {
        if(root == null) return null;
        str.append(root.val);
        if(root.left != null) {
            str.append("(");
            tree2str(root.left);
            str.append(")");
        } else {
            if(root.right == null) {
                return str.toString();
            } else {
                str.append("()");
            }
        }

        if(root.right == null) {
            return str.toString();
        } else {
            str.append("(");
            tree2str(root.right);
            str.append(")");
        }
        return str.toString();
    }
}